package LeetCode.Leet300_399.Leet320_329.Leet322;

/**
 * @ClassName Solution_1
 * @Author 孙天赐
 * @Date 2025/9/29 18:24
 * @Description TODO: 方法一   动态规划    12ms    89.62%
 */
class Solution_1 {
    public int coinChange(int[] coins, int amount) {
        if(coins.length == 0){
            return -1;
        }
        // 第i次循环，dp[j]的含义为：前i个面额的硬币，组成总金额j所需的最少硬币数
        int[] dp = new int[amount + 1];
        // 初始化
        for(int j = 1;j <= amount;j++){
            dp[j] = Integer.MAX_VALUE;
        }

        // 动态规划
        for(int i = 0;i < coins.length;i++){
            int money = coins[i];
            for(int j = money;j <= amount;j++){
                if(dp[j - money] != Integer.MAX_VALUE){
                    // 两者取较小值
                    // 1. 不使用当前硬币，dp[j]
                    // 2. 使用当前硬币，dp[j - money] + 1
                    dp[j] = Math.min(dp[j], dp[j - money] + 1);
                }

            }
        }

        return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
    }
}
